package Niuke;

import java.util.HashMap;


public class lrutest {

    int capacity;
    int size;
    lruDoubleList list;
    HashMap<Integer,lruNode> map;

    class lruNode{
        int key;
        int value;
        lruNode pre;
        lruNode next;

        lruNode(int k,int v){
            this.key=k;
            this.value=v;
        }
    }

    class lruDoubleList{
        lruNode tail;
        lruNode head;
    }

    public lrutest(int capacity) {
        this.size=0;
        this.capacity=capacity;
        list=new lruDoubleList();
        map=new HashMap<>();
    }

    public int get(int key) {
        if (map.containsKey(key)){
            move(map.get(key));
            return map.get(key).value;
        }else
            return -1;
    }

    public void put(int key, int value) {
        //存在当前key
        if (map.containsKey(key)){
            map.get(key).value=value;
            move(map.get(key));
        }else {
        //不存在当前key
            //lru满了
            if (size==capacity)
                removeFirst();
            lruNode lruNode = new lruNode(key, value);
            putNewNode(lruNode);
        }
    }

    //删除最近最久未使用
    //map中删除，list中删除
    public void removeFirst(){
        //list remove ,map remove
        lruNode head = list.head;
        lruNode next = head.next;
        if (next!=null){
            next.pre=null;
            head.next=null;
            map.remove(head.key,head);
            list.head=next;
        }else {
            map.remove(head.key,head);
            list.head=null;
            list.tail=null;
        }
        size--;
    }

    //放置新节点,list和map
    public void putNewNode(lruNode node){
        if (!map.containsKey(node.key)) {
            map.put(node.key, node);
            size++;
        }
        lruNode tail = list.tail;
        if (tail==null){
            list.tail=node;
            list.head=node;
        }else {
            tail.next=node;
            node.pre=tail;
            list.tail=node;
        }
    }

    //最新访问的，放在链表最后面 update list
    public void move(lruNode node){
        //pos is tail
        if (list.tail==node)
            return;
        //从原链表中切断
        //head
        if (list.head==node){
            lruNode next = node.next;
            node.next=null;
            next.pre=null;
            list.head=next;
        }else {
            //mid
            lruNode pre = node.pre;
            lruNode next = node.next;
            pre.next=next;
            next.pre=pre;
            node.next=null;
            node.pre=null;
        }
        putNewNode(node);
    }

    public static void main(String[] args) {
        lrutest lruCache = new lrutest(2);
        lruCache.put(1,1);
        lruCache.put(2,2);
        System.out.println(lruCache.get(1));
        lruCache.put(3,3);
        System.out.println(lruCache.get(2));
        lruCache.put(4,4);
        System.out.println(lruCache.get(1));
        System.out.println(lruCache.get(3));
        System.out.println(lruCache.get(4));
    }
}
